1493C - K-beautiful Strings - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;


int main()
{

	int t;
	int n,k;
	string str;
	cin>>t;
	while(t--){

		cin>>n>>k>>str;

		vector<int>cnt(26,0);
		for(auto ch:str){
			cnt[ch-'a']++;
		}

		int sum=0;
		bool flag=true;
		for(int i=0;i<26;i++){
			if(cnt[i]%k!=0){
				flag=false;	
			}
		}

		if(n%k!=0){
			cout<<-1<<endl;
			continue;
		}
		if(flag){
			cout<<str<<endl;
			continue;
		}


		for(int i=n-1;i>=0 && !flag;i--){
			cnt[str[i]-'a']--;
			for(int j=str[i]-'a'+1;j<26;j++){
				cnt[j]++;
				int need = 0;
				for(int ch=0;ch<26;ch++){
					need+=(k-cnt[ch]%k)%k;
				}
				if(need<=n-i-1){
					int pos=n-1;
					for(char ch='z';ch>='a';ch--){
						while(cnt[ch-'a']%k){
							str[pos--]=ch;
							cnt[ch-'a']++;
						}
					}
					while(pos>i){
						str[pos--]='a';
					}
					str[i]='a'+j;
					flag=true;
					break;
				}
				cnt[j]--;
			}
		}
		cout<<str<<endl;
	} 
	
}